Masala #1216

Har yili yangi yil bayramida elflar Qorboboning ustaxonasini rang-barang chiroqlar zanjiri bilan bezatadi. Bu yil ham elflar aynan shu ish bilan mashg'ul. Doimiy bir xillikdan zerikkan Qorbobo bu safar yangilik kiritishga qaror qildi: ba'zi chiroqlar bir xil rangda yonishi kerak, shunda ular jozibador ko'rinadi. Qorbobo elflarga aynan shunday topshiriq berdi. Tabiiyki, elflar rang-baranglikni yoqtiradi, shuning uchun elflar iloji boricha ko'proq turdagi ranglar bo'lishini xohlaydi. Qorboboning talablariga javob bergan holda, ko'pi bilan necha xil chiroq o'rnatish mumkin ekanligini aniqlashda elflarga yordam bering.

Kirishning birinchi qatorida n va m - zanjirdagi chiroqlar soni va Qorboboning talablari soni kiritiladi.

Keyingi \(m\) qatorning har birida Qorboboning talabi kiritiladi. Har bir qator uchta butun son - \(a_i, b_i, l_i\) dan iborat

Bunday uchlik shuni anglatadiki, zanjirning
\(\{a_i, \ldots, a_i + l_i - 1\}\) va \(\{b_i, \ldots, b_i + l_i - 1\}\) raqamli chiroqlardan iborat bo‘laklari bir xil bo‘lishi kerak.

Boshqacha aytganda, \(a_i\) va \(b_i\) raqamli chiroqlar bir xil rangda bo‘lishi kerak; xuddi shunday, \(a_i + 1\) va \(b_i + 1\), va hokazo, \(a_i + l_i - 1\) va \(b_i + l_i - 1\) gacha.

\(2 \le n \le 2000\)

\(1 \le m \le 2000\)

\(1 \le a_i, b_i, l_i;\; a_i \ne b_i;\; a_i, b_i \le n - l_i + 1\)

Elflar Qorboboning shartlarini bajargan holda ko'pi bilan necha xil turdagi chiroqlardan foydalana olishini chop eting.